Serveur d'exploration sur les relations entre la France et l'Australie

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Accelerating Lattice Reduction with FPGAs

Identifieur interne : 007349 ( Main/Exploration ); précédent : 007348; suivant : 007350

Accelerating Lattice Reduction with FPGAs

Auteurs : Jérémie Detrey [France] ; Guillaume Hanrot [France] ; Xavier Pujol [France] ; Damien Stehlé [Australie, France]

Source :

RBID : ISTEX:2900FDFB0BEF6C5C276B9C3D2F9414F9305194EF

Descripteurs français

English descriptors

Abstract

Abstract: We describe an FPGA accelerator for the Kannan–Fincke–Pohst enumeration algorithm (KFP) solving the Shortest Lattice Vector Problem (SVP). This is the first FPGA implementation of KFP specifically targeting cryptographically relevant dimensions. In order to optimize this implementation, we theoretically and experimentally study several facets of KFP, including its efficient parallelization and its underlying arithmetic. Our FPGA accelerator can be used for both solving stand-alone instances of SVP (within a hybrid CPU–FPGA compound) or myriads of smaller dimensional SVP instances arising in a BKZ-type algorithm. For devices of comparable costs, our FPGA implementation is faster than a multi-core CPU implementation by a factor around 2.12.

Url:
DOI: 10.1007/978-3-642-14712-8_8


Affiliations:


Links toward previous steps (curation, corpus...)


Le document en format XML

<record>
<TEI wicri:istexFullTextTei="biblStruct">
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="en">Accelerating Lattice Reduction with FPGAs</title>
<author>
<name sortKey="Detrey, Jeremie" sort="Detrey, Jeremie" uniqKey="Detrey J" first="Jérémie" last="Detrey">Jérémie Detrey</name>
</author>
<author>
<name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name>
</author>
<author>
<name sortKey="Pujol, Xavier" sort="Pujol, Xavier" uniqKey="Pujol X" first="Xavier" last="Pujol">Xavier Pujol</name>
</author>
<author>
<name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:2900FDFB0BEF6C5C276B9C3D2F9414F9305194EF</idno>
<date when="2010" year="2010">2010</date>
<idno type="doi">10.1007/978-3-642-14712-8_8</idno>
<idno type="url">https://api.istex.fr/document/2900FDFB0BEF6C5C276B9C3D2F9414F9305194EF/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000789</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000789</idno>
<idno type="wicri:Area/Istex/Curation">000789</idno>
<idno type="wicri:Area/Istex/Checkpoint">000C66</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000C66</idno>
<idno type="wicri:doubleKey">0302-9743:2010:Detrey J:accelerating:lattice:reduction</idno>
<idno type="wicri:Area/Main/Merge">007885</idno>
<idno type="wicri:Area/Main/Curation">007349</idno>
<idno type="wicri:Area/Main/Exploration">007349</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title level="a" type="main" xml:lang="en">Accelerating Lattice Reduction with FPGAs</title>
<author>
<name sortKey="Detrey, Jeremie" sort="Detrey, Jeremie" uniqKey="Detrey J" first="Jérémie" last="Detrey">Jérémie Detrey</name>
<affiliation wicri:level="3">
<country xml:lang="fr">France</country>
<wicri:regionArea>CARAMEL project-team, LORIA, INRIA / CNRS / Nancy Université, Campus Scientifique, BP 239, F-54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea>
<placeName>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name>
<affiliation wicri:level="1">
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire LIP, CNRS-ENSL-INRIA-UCBL, ÉNS Lyon, Université de Lyon, 46 Allée d’Italie, 69364, Lyon Cedex 07</wicri:regionArea>
<wicri:noRegion>69364, Lyon Cedex 07</wicri:noRegion>
<wicri:noRegion>Lyon Cedex 07</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Pujol, Xavier" sort="Pujol, Xavier" uniqKey="Pujol X" first="Xavier" last="Pujol">Xavier Pujol</name>
<affiliation wicri:level="1">
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire LIP, CNRS-ENSL-INRIA-UCBL, ÉNS Lyon, Université de Lyon, 46 Allée d’Italie, 69364, Lyon Cedex 07</wicri:regionArea>
<wicri:noRegion>69364, Lyon Cedex 07</wicri:noRegion>
<wicri:noRegion>Lyon Cedex 07</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
<affiliation wicri:level="1">
<country xml:lang="fr">Australie</country>
<wicri:regionArea>CNRS, Macquarie University and University of Sydney, Dpt. of Mathematics and Statistics, University of Sydney, 2006, NSW</wicri:regionArea>
<wicri:noRegion>NSW</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series>
<title level="s">Lecture Notes in Computer Science</title>
<imprint>
<date>2010</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc>
<textClass>
<keywords scheme="KwdEn" xml:lang="en">
<term>Actual number</term>
<term>Algorithm</term>
<term>Bottom layer</term>
<term>Clock cycles</term>
<term>Communication cost</term>
<term>Control unit</term>
<term>Corresponding subtree</term>
<term>Cryptography</term>
<term>Cryptology</term>
<term>Cryptosystems</term>
<term>Detrey</term>
<term>Enumerating vectors</term>
<term>Enumeration</term>
<term>Enumeration algorithm</term>
<term>Enumeration tree</term>
<term>Euclidean lattices</term>
<term>Fpga</term>
<term>Fpga accelerator</term>
<term>Fpga implementation</term>
<term>Fpgas</term>
<term>Gaussian</term>
<term>Gaussian approximation</term>
<term>Gaussian estimate</term>
<term>Gaussian heuristic</term>
<term>Granularity</term>
<term>Granularity level</term>
<term>Heidelberg</term>
<term>Heuristic</term>
<term>Homomorphic encryption</term>
<term>Ideal lattices</term>
<term>Implementation</term>
<term>Input basis</term>
<term>Integer part</term>
<term>Intel core</term>
<term>Lattice</term>
<term>Lattice attacks</term>
<term>Lattice problems</term>
<term>Lattice reduction</term>
<term>Lncs</term>
<term>Local variables</term>
<term>Master machine</term>
<term>Matrix</term>
<term>Memory requirements</term>
<term>Multiplier</term>
<term>Nguyen</term>
<term>Node</term>
<term>Parallel implementation</term>
<term>Parallelization</term>
<term>Parallelization technique</term>
<term>Partial sums</term>
<term>Performance estimations</term>
<term>Pohst enumeration algorithm</term>
<term>Possible values</term>
<term>Proc</term>
<term>Randomized reductions</term>
<term>Real number</term>
<term>Resource usage</term>
<term>Schmidt matrix</term>
<term>Short vectors</term>
<term>Shortest</term>
<term>Shortest lattice vector</term>
<term>Shortest lattice vector problem</term>
<term>Shortest vector</term>
<term>Shortest vector problem</term>
<term>Software</term>
<term>Software implementation</term>
<term>Solver</term>
<term>Space complexities</term>
<term>Speed grade</term>
<term>Sphere decoding</term>
<term>Springer</term>
<term>Squared norm</term>
<term>Stehl</term>
<term>Stoc</term>
<term>Subtree</term>
<term>Subtrees</term>
<term>Total traversal rate</term>
<term>Traversal</term>
<term>Traversal rate</term>
<term>Unit price</term>
<term>Whole enumeration tree</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en">
<term>Actual number</term>
<term>Algorithm</term>
<term>Bottom layer</term>
<term>Clock cycles</term>
<term>Communication cost</term>
<term>Control unit</term>
<term>Corresponding subtree</term>
<term>Cryptography</term>
<term>Cryptology</term>
<term>Cryptosystems</term>
<term>Detrey</term>
<term>Enumerating vectors</term>
<term>Enumeration</term>
<term>Enumeration algorithm</term>
<term>Enumeration tree</term>
<term>Euclidean lattices</term>
<term>Fpga</term>
<term>Fpga accelerator</term>
<term>Fpga implementation</term>
<term>Fpgas</term>
<term>Gaussian</term>
<term>Gaussian approximation</term>
<term>Gaussian estimate</term>
<term>Gaussian heuristic</term>
<term>Granularity</term>
<term>Granularity level</term>
<term>Heidelberg</term>
<term>Heuristic</term>
<term>Homomorphic encryption</term>
<term>Ideal lattices</term>
<term>Implementation</term>
<term>Input basis</term>
<term>Integer part</term>
<term>Intel core</term>
<term>Lattice</term>
<term>Lattice attacks</term>
<term>Lattice problems</term>
<term>Lattice reduction</term>
<term>Lncs</term>
<term>Local variables</term>
<term>Master machine</term>
<term>Matrix</term>
<term>Memory requirements</term>
<term>Multiplier</term>
<term>Nguyen</term>
<term>Node</term>
<term>Parallel implementation</term>
<term>Parallelization</term>
<term>Parallelization technique</term>
<term>Partial sums</term>
<term>Performance estimations</term>
<term>Pohst enumeration algorithm</term>
<term>Possible values</term>
<term>Proc</term>
<term>Randomized reductions</term>
<term>Real number</term>
<term>Resource usage</term>
<term>Schmidt matrix</term>
<term>Short vectors</term>
<term>Shortest</term>
<term>Shortest lattice vector</term>
<term>Shortest lattice vector problem</term>
<term>Shortest vector</term>
<term>Shortest vector problem</term>
<term>Software</term>
<term>Software implementation</term>
<term>Solver</term>
<term>Space complexities</term>
<term>Speed grade</term>
<term>Sphere decoding</term>
<term>Springer</term>
<term>Squared norm</term>
<term>Stehl</term>
<term>Stoc</term>
<term>Subtree</term>
<term>Subtrees</term>
<term>Total traversal rate</term>
<term>Traversal</term>
<term>Traversal rate</term>
<term>Unit price</term>
<term>Whole enumeration tree</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr">
<term>Cryptographie</term>
<term>Logiciel</term>
<term>Prix unitaire</term>
</keywords>
</textClass>
<langUsage>
<language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="en">Abstract: We describe an FPGA accelerator for the Kannan–Fincke–Pohst enumeration algorithm (KFP) solving the Shortest Lattice Vector Problem (SVP). This is the first FPGA implementation of KFP specifically targeting cryptographically relevant dimensions. In order to optimize this implementation, we theoretically and experimentally study several facets of KFP, including its efficient parallelization and its underlying arithmetic. Our FPGA accelerator can be used for both solving stand-alone instances of SVP (within a hybrid CPU–FPGA compound) or myriads of smaller dimensional SVP instances arising in a BKZ-type algorithm. For devices of comparable costs, our FPGA implementation is faster than a multi-core CPU implementation by a factor around 2.12.</div>
</front>
</TEI>
<affiliations>
<list>
<country>
<li>Australie</li>
<li>France</li>
</country>
<region>
<li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
</list>
<tree>
<country name="France">
<region name="Grand Est">
<name sortKey="Detrey, Jeremie" sort="Detrey, Jeremie" uniqKey="Detrey J" first="Jérémie" last="Detrey">Jérémie Detrey</name>
</region>
<name sortKey="Detrey, Jeremie" sort="Detrey, Jeremie" uniqKey="Detrey J" first="Jérémie" last="Detrey">Jérémie Detrey</name>
<name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name>
<name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name>
<name sortKey="Pujol, Xavier" sort="Pujol, Xavier" uniqKey="Pujol X" first="Xavier" last="Pujol">Xavier Pujol</name>
<name sortKey="Pujol, Xavier" sort="Pujol, Xavier" uniqKey="Pujol X" first="Xavier" last="Pujol">Xavier Pujol</name>
<name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
</country>
<country name="Australie">
<noRegion>
<name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007349 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 007349 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Asie
   |area=    AustralieFrV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:2900FDFB0BEF6C5C276B9C3D2F9414F9305194EF
   |texte=   Accelerating Lattice Reduction with FPGAs
}}

Wicri

This area was generated with Dilib version V0.6.33.
Data generation: Tue Dec 5 10:43:12 2017. Site generation: Tue Mar 5 14:07:20 2024